/**
 * 数组相关的方法
 */

/**
 * 树节点接口
 */
export interface TreeNodes<T extends Node> {
  /**
   * 根节点
   */
  value: T[];
  /**
   * 树的根节点数量
   */
  rootCount: number;
  /**
   * 树的根节点数量
   */
  isOneRoot: boolean;
  /**
   * 是否是根节点
   */
  isRoot(node: T): boolean;
  /**
   * 遍历树
   */
  traverseTree: (callback: (node: T) => void) => void;
  /**
   * 获取树的深度
   */
  getTreeDepth: () => number;
  /**
   * 获取树的叶子节点
   */
  getTreeLeaf: () => T[];
  /**
   * 获取树的路径
   */
  getTreePath: (node: T) => T[];
  /**
   * 获取树的节点
   */
  getTreeNode: (id: string) => T | undefined;
  /**
   * 获取树的叶子节点映射
   */
  getTreeLeafNodeMap: () => Map<string, T>;
}
/**
 * 树节点
 */
export type Node = {
  parent?: Node | null;
  children?: Node[] | null;
  id: string;
};

/**
 * 创建树
 */
export const createTreeNodes = <T extends Node>(value: T[]): TreeNodes<T> => {
  const o: TreeNodes<T> = {
    value: value,
    get rootCount() {
      return this.value.length;
    },
    get isOneRoot() {
      return this.rootCount === 1;
    },
    isRoot(node: T) {
      return this.value.includes(node as T);
    },

    traverseTree(callback: (node: T) => void) {
      this.value.forEach((node) => {
        traverseTree(node, callback);
      });
    },

    getTreeDepth() {
      return Math.max(...this.value.map((node) => getTreeDepth(node)));
    },

    getTreeLeaf() {
      return this.value.flatMap((node) => getTreeLeafs(node));
    },

    getTreeNode(id: string) {
      const getNode = (node: Node): Node | undefined => {
        if (node.id === id) return node;
        if (node.children) {
          for (const child of node.children) {
            const result = getNode(child);
            if (result) return result;
          }
        }
      };
      return this.value.find((item) => getNode(item));
    },

    getTreePath(node: T) {
      const path: T[] = [];
      let current: T | null | undefined = node;
      while (current) {
        path.push(current);
        current = current.parent as T;
      }
      return path.reverse();
    },
    getTreeLeafNodeMap() {
      const map = new Map<string, T>();
      this.getTreeLeaf().forEach((item) => {
        map.set(item.id, item);
      });
      return map;
    },
  };
  return o;
};

/**
 * 遍历树
 * @param root 根节点
 * @param callback 回调函数
 */
export const traverseTree = <T extends Node>(
  root: T,
  callback: (node: T) => void,
) => {
  callback(root);
  if (root.children) {
    root.children.forEach((child) => {
      traverseTree(child as T, callback);
    });
  }
};

/**
 * 获取树的深度
 * @param root 根节点
 * @returns 深度
 */
export const getTreeDepth = (root: Node): number => {
  if (!root.children || root.children.length === 0) {
    return 1;
  }

  let maxChildDepth = 0;
  root.children.forEach((child) => {
    maxChildDepth = Math.max(maxChildDepth, getTreeDepth(child));
  });

  return maxChildDepth + 1;
};

/**
 * 树节点转Map
 * @param node 树节点
 * @param map Map
 * @returns Map
 */
export const treeNodeToMap = (
  node: Node,
  map?: Map<string, Node>,
): Map<string, Node> => {
  map = map ?? new Map();
  map.set(node.id, node);
  node.children?.forEach((child) => {
    treeNodeToMap(child, map);
  });
  return map;
};

/**
 * 根据ID在树结构中查找节点
 *
 * 该函数通过深度优先搜索在树结构中查找指定ID的节点。
 *
 * @param id - 要查找的节点ID
 * @param node - 树的根节点
 * @returns 找到的节点，如果未找到则返回undefined
 *
 * @example
 * ```typescript
 * const tree = {
 *   id: '1',
 *   parent: null,
 *   children: [
 *     { id: '2', parent: null, children: null },
 *     { id: '3', parent: null, children: null }
 *   ]
 * };
 * const node = findNodeById('2', tree);
 * console.log(node?.id); // '2'
 * ```
 *
 * @since 1.0.0
 */
export const findNodeById = (id: string, node: Node): Node | undefined => {
  // 参数验证
  if (!id || !node) {
    return undefined;
  }

  // 检查当前节点是否匹配
  if (node.id === id) {
    return node;
  }

  // 递归检查子节点
  if (node.children && node.children.length > 0) {
    for (const child of node.children) {
      // 确保child不为null或undefined
      if (child) {
        const found = findNodeById(id, child);
        if (found) {
          return found;
        }
      }
    }
  }

  return undefined;
};

/**
 * 根据条件过滤树节点
 * @param node 树节点
 * @param predicate 过滤条件函数
 * @returns 过滤后的树节点
 */
export const filterTree = (
  node: Node,
  predicate: (node: Node) => boolean,
): Node | null => {
  // 如果当前节点不满足条件，直接返回null
  if (!predicate(node)) {
    // 但我们需要检查子节点是否有满足条件的
    if (!node.children || node.children.length === 0) {
      return null;
    }

    // 在子节点中查找满足条件的节点
    for (const child of node.children) {
      const filtered = filterTree(child, predicate);
      if (filtered) {
        return filtered;
      }
    }

    return null;
  }

  // 当前节点满足条件，创建副本
  const newNode: Node = {
    ...node,
    parent: null, // 新节点没有父节点
    children: null,
  };

  // 递归处理子节点
  if (node.children) {
    const filteredChildren: Node[] = [];
    node.children.forEach((child) => {
      const filteredChild = filterTree(child, predicate);
      if (filteredChild) {
        // 设置父节点引用
        filteredChild.parent = newNode;
        filteredChildren.push(filteredChild);
      }
    });
    if (filteredChildren.length > 0) {
      newNode.children = filteredChildren;
    }
  }

  return newNode;
};

/**
 * 克隆树结构
 * @param node 需要克隆的树节点
 * @returns 克隆后的树节点
 */
export const cloneTree = (node: Node): Node => {
  // 创建当前节点的副本
  const newNode: Node = {
    ...node,
    parent: null, // 注意：克隆的节点暂时保持parent引用，根据需要可以在调用后处理
    children: null,
  };

  // 递归处理子节点
  if (node.children) {
    const clonedChildren: Node[] = [];
    node.children.forEach((child) => {
      const clonedChild = cloneTree(child);
      // 设置正确的父子关系
      clonedChild.parent = newNode;
      clonedChildren.push(clonedChild);
    });
    newNode.children = clonedChildren;
  }

  return newNode;
};

/**
 * 将树结构扁平化为节点数组
 * @param node 树节点
 * @returns 扁平化后的节点数组
 */
export const flattenTree = (node: Node): Node[] => {
  const result: Node[] = [];

  // 使用 traverseTree 遍历所有节点并添加到结果数组中
  traverseTree(node, (currentNode) => {
    // 创建节点副本并清除父子关系以避免循环引用
    const nodeCopy: Node = {
      ...currentNode,
      parent: null, // 不复制parent引用以避免循环引用问题
      children: null, // 不复制children引用
    };
    result.push(nodeCopy);
  });

  return result;
};

type unstdNode = Record<string, unknown> & {
  children?: unknown[] | null;
  id: string;
  parent?: unknown | null;
};

/**
 * 格式化标准树节点
 * @param source 源节点
 * @returns 格式化后的节点
 */
export const formatStdNode = (source: unstdNode): Node => {
  const { children, ...rest } = source;
  const node = {
    ...rest,
    parent: null,
    children: null,
    id: source.id,
  } as Node;
  if (children) {
    node.children = children.map(
      (child): Node => formatStdNode(child as unstdNode),
    );
    // 设置子节点的parent引用
    node.children.forEach((child) => {
      child.parent = node;
    });
  }

  return node;
};

/**
 * 获取树的所有叶子节点
 * @param node 树节点
 * @returns 叶子节点数组
 */
export const getTreeLeafs = <T extends Node>(node: T): T[] => {
  if (!node.children) {
    return [node];
  }
  return node.children.flatMap((child) => getTreeLeafs(child as T));
};
